package com.example.arithmeticleetcode.leetcode.September;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-09-30 11:31
 **/
public class Demo24 {

    public static void main(String[] args) {
        System.out.println(removeDuplicates("abbaca"));
        System.out.println(removeDuplicates("cdcabbacedc"));

        System.out.println(removeDuplicates2("abbaca"));
        System.out.println(removeDuplicates2("cdcabbacedc"));
    }

    public static String removeDuplicates(String S) {
        if (S.length() < 2) {
            return S;
        }
        List<Character> list = new ArrayList<>();
        for (int i = 0, len = S.length(); i < len; i++) {
            list.add(S.charAt(i));
        }
        int endIndex = S.length() - 1;
        int beforeEndIndex = S.length() - 2;
        while (beforeEndIndex >= 0) {
            if (list.get(endIndex) == list.get(beforeEndIndex)) {
                list.remove(endIndex);
                list.remove(beforeEndIndex);
                endIndex = list.size() - 1;
                beforeEndIndex = list.size() - 2;
            } else {
                endIndex--;
                beforeEndIndex--;
            }
        }
        System.out.println(list);
        StringBuilder sb = new StringBuilder("");
        for (Character character : list) {
            sb.append(character);
        }
        return sb.toString();
    }

    public static String removeDuplicates2(String S) {
        char[] chars = new char[S.length()];
        int index = 0;
        for (int i = 0; i < S.length(); i++) {
            if (index != 0 && S.charAt(i) == chars[index - 1]) {
                index--;
            } else {
                chars[index++] = S.charAt(i);
            }
        }
        return new String(chars, 0, index);
    }
}
